package binarytree;

import java.util.LinkedList;
import java.util.Queue;

public class IsCompleteBinaryTree {

  /**
   * 判断是否是一颗合法的完全二叉树<br>
   * 完全二叉树的定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，<br>
   *     如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树<br>
   *  满二叉树的定义：每一层的节点数目都达到最大。满二叉树一定是是完全二叉树，反之不然。<br>
   *  完全二叉树的判定方法：<br>
   *      &nbsp 1. 如果树为空，直接返回错 <br>
   *      &nbsp 2. 如果树不为空，使用 Queue 层序遍历二叉树 <br>
   *      &nbsp 3. 如果一个节点的左右孩子都不为空，则 pop 该节点，并将其左右孩子加入队列 <br>
   *      &nbsp 4. 如果一个节点的左孩子为空，右孩子不为空，该树一定不是完全二叉树 <br>
   *      &nbsp 5. 如果一个节点的左孩子不为空，右孩子不为空，或者左右孩子都为空，则该节点之后的所有节点都要为叶子节点，该树才是完全二叉树 <br>
   *
   * @param root
   * @return
   */
  public boolean isCompleteBinaryTrre(TreeNode root) {
    if (root == null) {
      return false;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      //如果左节点为空，有节点不为空，这肯定不是完全二叉树
      if (node.left == null && node.right != null) {
        return false;
        //如果右节点为空，左节点不为空或者是左右节点都为空，则说明接下来的系节点应该都是叶子节点
      } else if ((node.left != null && node.right == null) ||
              (node.left == null && node.right == null)) {
        if (node.left != null) {
          queue.offer(node.left);
        }
        while (!queue.isEmpty()) {
          TreeNode top = queue.poll();
          if (top.left == null && top.right == null) {

          } else {
            return false;
          }
        }
        //当node的左节点或者是右节点都不为空时，则将其左右节点添加进队列中
      } else {
        queue.offer(node.left);
        queue.offer(node.right);
      }
    }
    return true;
  }
}
